ОЦІНКА СКЛАДНОСТІ АЛГОРИТМІВ

Інформація про навчальний заклад

ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано

Інформація про роботу

Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів

Частина тексту файла

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №1 з навчальної дисципліни “Програмування складних алгоритмів” Тема: ОЦІНКА СКЛАДНОСТІ АЛГОРИТМІВ Мета: Метою лабораторної роботи є отримання практичних навичок визначати часову складність алгоритму. Навчитися будувати алгоритми з мінімальною часовою складністю для вирішення поставлених задач. Теоретична частина Алгоритм – це скінченна послідовність команд, які треба виконати над вхідними даними для отримання результату. Основними мірами обчислювальною складності алгоритмів є: Часова складність алгоритму в комп'ютерних науках є обчислювальною складністю алгоритму, яка описує час потрібний для виконання алгоритму. Вона зазвичай визначається шляхом підрахунку кількості елементарних операцій, виконуваних алгоритмом, при цьому вважають, що кожна елементарна операція виконується за фіксовану кількість часу. Таким чином, кількість часу і кількість елементарних операцій, необхідних для виконання алгоритму, відрізняються постійним множником. Ємнісна складність, яка характеризує пам'ять, необхідну для виконання алгоритму. Часова та ємнісна складність тісно пов'язані між собою. Обидві є функціями від розміру вхідних даних. Структурна складність - характеристика кількості керуючих структур в алгоритмі і специфіки їх взаємного розташування. Когнітивна складність - характеристика доступності алгоритму для розуміння фахівцями прикладних областей. Виділяють такі основні класи алгоритмів: логарифмічні: f(n) = O (log2n); лінійні: f(n) = O (n); поліноміальні: f(n) = O (nm); тут m - натуральне число, більше від одиниці; при m = 1 алгоритм є лінійним; експоненційні: f(n) = O (an); a - натуральне число, більше від одиниці. Для однієї й тієї ж задачі можуть існувати алгоритми різної складності. Часто буває і так, що більш повільний алгоритм працює завжди, а більш швидкий - лише за певних умов. Загальне завдання Сформувати двовимірний масив цілих чисел, використовуючи датчик випадкових чисел. Використати оголошення масиву на n елементів (кількість елементів задавати з екрану). Провести оцінку часової складності алгоритму, використовуючи О-символіку в найгіршому або/і в середньому. Порівняти час роботи та кількість ітерацій/кількість кроків роботи програми з різною розмірністю масиву (10x10, 50x50, 100x100, 500x500). Оцінку часу роботи навести у вигляді графіка, або таблиці. Завдання 1 / Завдання 2 / / Результат роботи Завдання 1  Розмір матриці n Кількість ітерацій Час виконання  10 120 - 220 8 мс  50 2600 - 5100 12 мс  100 10200 - 20200 14 мс  500 251000 - 501000 19 мс   Завдання 2  Розмір матриці n Кількість ітерацій Час виконання  10 40 <1 мс  50 700 <1 мс  100 2650 1 мс  500 63250 6 мс   Блок-схема / Завдання 1 / Завдання 2 / Висновок: було написано програму, що створює двовимірний масив, виконує певні зміни та заміряє час виконання алгоритму. Програму було досліджено на швидкість роботи та кількість ітерацій при виконуванні кожного завдання та при різних величинах масиву. Час виконання алгоритму було максимально мінімізовано. Програмний код import java.util.*; public class LR1 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("Введіть розмір масиву: "); int n = scanner.nextInt(); int[][] arr = new int[n][n]; System.out.println("Початковий масив"); for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length; j++) { arr[i][j] = (int) (Math.random() * 50); System.out.print(arr[i][j] + "\t"); } System.out.println(); } System.out.println("Введіть номер завдання(1 або 2): "); n = scanner.nextInt(); if(n==1){ System.out.println("--------Завдання 1--------"); long firstTimeMills = System.currentTimeMillis(); int sum =...
Антиботан аватар за замовчуванням

10.07.2023 07:07

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини